package com.yulan.Tree;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 297. 二叉树的序列化与反序列化 dfs
 */
public class LeetCode_297_dfs {
    private class Codec{
        private String reserialize(TreeNode root, String str){
            if(root == null){
                str += "null,";
            }else{
                str += root.val+",";
                str = reserialize(root.left,str);
                str = reserialize(root.right,str);
            }
            return str;
        }

        public String serialize(TreeNode root) {
            return reserialize(root,"");
        }

        private TreeNode redeserialize(List<String> list){
            if(list.get(0).equals("null")){
                list.remove(0);
                return null;
            }
            TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            root.left = redeserialize(list);
            root.right = redeserialize(list);

            return root;
        }

        // Decodes your encoded data to Tree.
        public TreeNode deserialize(String data) {
            String[] datas = data.split(",");
            List<String> list = new LinkedList<>(Arrays.asList(datas));
            return redeserialize(list);
        }
    }

    public void outTree(TreeNode root){
        if(root!=null){
            System.out.print(root.val+" ");
            outTree(root.left);
            outTree(root.right);
        }
    }

    @Test
    public void test(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;

        Codec codec = new Codec();

        String str = codec.serialize(node1);
        System.out.println(str);

        TreeNode root = codec.deserialize(str);
        outTree(root);
    }
}
